Gordon–Newell theorem

In queueing theory, a discipline within the mathematical theory of probability, the Gordon–Newell theorem is an extension of Jackson's theorem from open queueing networks to closed queueing networks of exponential servers.[1] We cannot apply Jackson's theorem to closed networks because the queue length at a node in the closed network is limited by the population of the network. The Gordon–Newell theorem calculates the open network solution and then eliminates the infeasible states by renormalizing the probabilities. Calculation of the normalizing constant makes the treatment more awkward as the whole state space must be enumerated.[2] Buzen's algorithm or mean value analysis can be used to calculate the normalizing constant more efficiently.

Contents

Definition of a Gordon–Newell network

A network of m interconnected queues is known as a Gordon–Newell network[3] or closed Jackson network[4] if it meets the following conditions:

  1. the network is closed (no customers can enter or leave the network),
  2. all service times are exponentially distributed and the service discipline at all queues is FCFS,
  3. a customer completing service at queue i will move to queue j with probability P_{ij}, with the P_{ij} such that \scriptstyle{\sum_{j =1}^m P_{ij} = 1},
  4. the utilization of all of the queues is less than one.

Theorem

In a closed Gordon–Newell network of m queues, with a total population of K individuals, write \scriptstyle{(k_1,k_2,\ldots,k_m)} (where ki is the length of queue i) for the state of the network and S(K, m) for the state space

S(K,m) = \{ \mathbf{k} \in \mathbb{Z}^m \text{ such that } \sum_{i=1}^m k_i = K \text{ and } k_i \geq 0 \forall i\}.

Then the equilibrium state probability distribution exists and is given by

\pi (k_1,k_2,\ldots,k_m) = \frac{1}{G(K)} \prod_{i=1}^m \left( \frac{e_i}{\mu_i} \right)^{k_i}

where service times at queue i are exponentially distributed with parameter μi. The normalizing constant G(K) is given by

G(K) = \sum_{\mathbf{k} \in S(K,m)} \prod_{i=1}^{m} \left( \frac{e_i}{\mu_i} \right)^{k_i} ,

and ei is the visit ratio, calculated by solving the simultaneous equations

e_i = \sum_{j=1}^m e_j p_{ji} \text{ for }1 \leq i \leq m. \,

See also

References

  1. ^ William J. Gordon and Gordon F. Newell (1967) Closed queueing systems with exponential servers in Operations Research 15 (2), 254–65
  2. ^ Andreas Willig A Short Introduction to Queueing Theory p. 33 Technical University Berlin, Telecommunication Networks Group, July 21 1999
  3. ^ Daduna, H. (1982). "Passage Times for Overtake-Free Paths in Gordon-Newell Networks". Advances in Applied Probability 14 (3): 672–686. doi:10.2307/1426680.  edit
  4. ^ Gong, Q.; Lai, K. K.; Wang, S. (2008). "Supply chain networks: Closed Jackson network models and properties". International Journal of Production Economics 113 (2): 567. doi:10.1016/j.ijpe.2007.10.013.  edit